package aco;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

// insertion heuristic
public class InsertionHeuristic {

    // 插入类（存储将一个城市插入到一个位置的各种信息）
    static class Insertion {
        //id of the unrouted customer that should be inserted in a route in the best feasible insertion place
        int customer;

        //id of the route or the index of the tour given by the best feasible insertion place
        int indexTour;

        //the previous node from the selected tour given by the best feasible insertion place
        //the unrouted customer will be inserted in the the tour having the index = indexTour and in front
        //of this node/customer/city
        int previousNode; // 将城市插入到这个位置。也就是说插入城市后，插入城市在这个城市的前面

        //computed value for the metric for a certain insertion place,
        // considered when deciding which is the best feasible insertion place for an unrouted customer
        double score; // c1的评分

        public Insertion() {
        }

        public Insertion(int customer_, int indexTour_, int previousNode_, double score_) {
            this.customer = customer_;
            this.indexTour = indexTour_;
            this.previousNode = previousNode_;
            this.score = score_;
        }

        public int getCustomer() {
            return customer;
        }

        public int getIndexTour() {
            return indexTour;
        }

        public int getPreviousNode() {
            return previousNode;
        }

        public double getScore() {
            return score;
        }

    }

    /**
     * insertion heuristic
     * 插入启发式方法，将节点插入到已有路径的城市与城市之间
     * 计算C1，得到每个未访问城市的Insertion类集合；
     * 计算C2，从所有未访问城市的Insertion类集合中找出最优的对象，执行插入操作。
     *
     * @param unvisitedNodes：未访问的城市集合
     * @param startIndexTour：开始遍历的路径编号
     * @param startPos：每条路径的开始位置的集合。大小应该是a.usedVehicles
     */
    static void insertUnroutedCustomers(Ants.Ant a, VRPTW vrp, ArrayList<Integer> unvisitedNodes, int startIndexTour, ArrayList<Integer> startPos) {
        boolean ok = true;
        double c11, c12, c13, c1, c1_, c2, value1, value2, value3, value4, earliestTime, latestTime;
        double bestC1Score = Double.MAX_VALUE;
        double bestC2Score = Double.MAX_VALUE;
        double arrivalTime, beginService = 0.0, newArrivalTime, newBeginService, oldBeginService, newQuantity, newDistance;
        int previousCity, nextCity, bestPos = 1, bestCustomer, bestIndexTour = 0, bestIndexInsertion = 0;
        int cust;
        double mu = 1.0, alfa1 = 0.1, alfa2 = 0.9, alfa3 = 0.2, lambda = 2.0;  //alfa1 = 0.1, alfa2 = 0.9
        ArrayList<Request> reqList = vrp.getRequests();
        Insertion ins, bestInsertion;
        int startIndex = 0;

        // 未指定路径的客户，最佳的插入位置的集合，最佳插入的集合
        // it contains for each unrouted customer its best feasible insertion place
        // this list is used when deciding the best unrouted customer to be inserted in the unfeasible solution
        ArrayList<Insertion> bestInsertions = new ArrayList<Insertion>();

        // visited<城市编号, 是否被访问>
        // keep track of nodes (customers) inserted/included in the solution by the insertion heuristic
        HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>(unvisitedNodes.size());
        for (int node : unvisitedNodes) {
            visited.put(node, false);
        }

        // 计算从路径startIndexTour开始的，每条路径中每个城市节点的，最早到达时间和最迟到达时间
        computeRouteVariables(a, vrp, startIndexTour);

        // 尝试将所有城市插入到现有路径中
        while (ok) {
            if (bestInsertions != null && bestInsertions.size() > 0) {
                bestInsertions.clear();
            }
            // Find the best possible feasible position to insert an unrouted customer into a tour, then insert it and update the score

            // 1.遍历每个未访问的城市，customer为城市编号（为customer城市寻找最佳的插入路径的最佳插入位置，也就是通过C1计算bestInsertions）
            // 生成[bestInsetions]集合
            for (int customer : unvisitedNodes) { // 遍历待插入城市
                if (!visited.get(customer)) {
                    bestC1Score = Double.MAX_VALUE;
                    // 1.1对城市customer，遍历路径，寻找其最合适的插入路径的插入位置
                    for (int indexTour = startIndexTour; indexTour < a.usedVehicles; indexTour++) {
                        // 路径indexTour中开始寻找的位置
                        if (indexTour > startPos.size() - 1) {
                            startIndex = 1;
                        } else {
                            startIndex = startPos.get(indexTour) + 1;
                        }
                        // check for a feasible insertion place within the considered tour
                        for (int pos = startIndex; pos < a.tours.get(indexTour).size(); pos++) { // 遍历路径中每个位置
                            if (isFeasibleInsertion(a, vrp, customer, indexTour, pos - 1, pos)) {
                                // compute the score (value) for the c1 metric
                                previousCity = a.tours.get(indexTour).get(pos - 1);
                                nextCity = a.tours.get(indexTour).get(pos);
                                c11 = VRPTW.instance.distance[previousCity + 1][customer + 1] + VRPTW.instance.distance[customer + 1][nextCity + 1] - mu * VRPTW.instance.distance[previousCity + 1][nextCity + 1];
                                arrivalTime = a.beginService[previousCity + 1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][customer + 1];
                                beginService = Math.max(arrivalTime, reqList.get(customer + 1).getStartWindow());
                                newArrivalTime = beginService + reqList.get(customer + 1).getServiceTime() + VRPTW.instance.distance[customer + 1][nextCity + 1];
                                newBeginService = Math.max(newArrivalTime, reqList.get(nextCity + 1).getStartWindow());
                                oldBeginService = a.beginService[nextCity + 1];
                                c12 = newBeginService - oldBeginService;
                                c1 = alfa1 * c11 + alfa2 * c12;
                                if (c1 < bestC1Score) {
                                    bestC1Score = c1;
                                    bestIndexTour = indexTour;
                                    bestPos = pos;
                                }
                            }
                        }
                    }
                    // 2.2找到了最佳的插入路径的插入位置，则创建Insertion类
                    // we have a best feasible insertion position for the unrouted node denoted by "customer"
                    if (bestC1Score != Double.MAX_VALUE) {
                        ins = new Insertion(customer, bestIndexTour, bestPos, bestC1Score);
                        bestInsertions.add(ins);
                    }
                }
            }

            // 2.通过计算并比较C2的值，找到bestInsetions集合中的最佳Insertion
            // decide the best customer to be inserted in the solution
            bestC2Score = Double.MAX_VALUE;
            Insertion insert;
            if (bestInsertions != null && bestInsertions.size() > 0) {
                for (int i = 0; i < bestInsertions.size(); i++) {
                    insert = bestInsertions.get(i);
                    cust = insert.getCustomer();
                    c1_ = insert.getScore();
                    c2 = lambda * VRPTW.instance.distance[0][cust + 1] - c1_;
                    if (c2 < bestC2Score) {
                        bestC2Score = c2;
                        bestIndexInsertion = i;
                    }
                }
            }

            // 3.如果找到了最佳的Insertion，则将customer城市插入到路径
            // we have the best customer to be inserted in the solution,
            // now we should perform the insertion of the selected best customer
            if (bestC2Score != Double.MAX_VALUE) {
                bestInsertion = bestInsertions.get(bestIndexInsertion);
                bestCustomer = bestInsertion.getCustomer();
                bestIndexTour = bestInsertion.getIndexTour();
                bestPos = bestInsertion.getPreviousNode();

                // 3.1 更改蚂蚁类中的一些变量值
                a.tours.get(bestIndexTour).add(bestPos, bestCustomer);
                a.visited[bestCustomer] = true;
                a.toVisit--;
                newQuantity = a.currentQuantity.get(bestIndexTour) + reqList.get(bestCustomer + 1).getDemand();
                a.currentQuantity.set(bestIndexTour, newQuantity);
                visited.put(bestCustomer, true);

                // 3.2 更新更新插入城市的最早到达时间和最迟到达时间
                // update earliest time and latest time lists to include the value for the newly inserted customer
                previousCity = a.tours.get(bestIndexTour).get(bestPos - 1);
                nextCity = a.tours.get(bestIndexTour).get(bestPos + 1);
                value1 = new Double(reqList.get(bestCustomer + 1).getStartWindow());
                value2 = a.earliestTime.get(bestIndexTour).get(bestPos - 1) + VRPTW.instance.distance[previousCity + 1][bestCustomer + 1] + reqList.get(previousCity + 1).getServiceTime();
                earliestTime = Math.max(value1, value2);
                value3 = new Double(reqList.get(bestCustomer + 1).getEndWindow());
                value4 = a.latestTime.get(bestIndexTour).get(bestPos) - VRPTW.instance.distance[bestCustomer + 1][nextCity + 1] - reqList.get(bestCustomer + 1).getServiceTime();
                latestTime = Math.min(value3, value4);
                a.earliestTime.get(bestIndexTour).add(bestPos, earliestTime);
                a.latestTime.get(bestIndexTour).add(bestPos, latestTime);

                // 3.3 更新插入城市。序列之前城市的最迟到达时间，序列之后城市的最早到达时间
                updateRouteVariables(a, vrp, bestInsertion);

                // 3.4 每个城市的到达时间（开始服务时间），每条路径的末端城市的到达时间
                // update the begin service times for the nodes that come after the inserted customer on the route
                // also update the begin service time for the inserted node itself
                for (int j = bestPos; j < a.tours.get(bestIndexTour).size(); j++) {
                    previousCity = a.tours.get(bestIndexTour).get(j - 1);
                    cust = a.tours.get(bestIndexTour).get(j);
                    arrivalTime = a.beginService[previousCity + 1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][cust + 1];
                    beginService = Math.max(arrivalTime, reqList.get(cust + 1).getStartWindow());
                    a.beginService[cust + 1] = beginService;
                }
                a.currentTime.set(bestIndexTour, beginService);
                ok = true;
            }

            // 4.如果不能再找打任何一个未访问城市可以执行插入操作，则跳出循环
            else {
                ok = false;
            }
        }
    }

    /* 计算蚂蚁a的每条路径中的每个城市的，可接受的，可实现的，最早到达时间，最迟到达时间 */
    static void computeRouteVariables(Ants.Ant a, VRPTW vrp, int startTourIndex) {
        // for every customer already included in the solution, compute route variables (earliest time a
        // delivery can be made at a customer and the latest time a delivery can be made at a customer)
        // used when checking feasibility of an insertion
        // 计算所得的最迟到达时间和最早到达时间都是可以接受的，不能在时间时间窗范围之外。

        int city, previousCity, nextCity;
        double value, value1, value2;
        ArrayList<Request> reqList = vrp.getRequests();

        // 1.计算请求城市集合中，规划好后的，每个城市的最早到达时间（从前往后算）
        //move forward in every tour and compute the values for the earliest time
        for (int index = startTourIndex; index < a.usedVehicles; index++) {
            int tourLength = a.tours.get(index).size();
            if (a.earliestTime == null) {
                System.out.println("Earliest time is null");
            }
            a.earliestTime.add(index, new ArrayList<Double>(tourLength));
            for (int i = 0; i < tourLength; i++) {  // i代表的是城市在路径中的序号，不是城市编号
                city = a.tours.get(index).get(i);  // 当前的城市编号
                // the current city (customer) is the depot
                if (((city + 1) == 0) && (i == 0)) {
                    value = new Double(reqList.get(0).getStartWindow());
                    a.earliestTime.get(index).add(i, value);
                } else {
                    previousCity = a.tours.get(index).get(i - 1);  // 前一个城市的编号
                    value1 = new Double(reqList.get(city + 1).getStartWindow()); // 当前城市的时间窗开启时间
                    value2 = a.earliestTime.get(index).get(i - 1) + VRPTW.instance.distance[previousCity + 1][city + 1] + reqList.get(previousCity + 1).getServiceTime();
                    value = Math.max(value1, value2);
                    a.earliestTime.get(index).add(i, value);
                }
            }
        }

        // 2.计算请求城市集合中，已经全都安排好的，最迟到达时间（从后往前算）
        // move backward in every tour and compute the values for the latest time
        for (int index = startTourIndex; index < a.usedVehicles; index++) {
            int tourLength = a.tours.get(index).size();
            // 生成一个可变列表，列表长度为tourLength，列表中每个元素的值为0.0
            // 因为本段是从后往前数的，所以要提前生成好了这些
            a.latestTime.add(index, new ArrayList<Double>(Collections.nCopies(tourLength, 0.0)));
            for (int i = tourLength - 1; i >= 0; i--) {  // 从后往前数
                city = a.tours.get(index).get(i);  // 当前城市的编号
                if (i == tourLength - 1) {  // 路径末端的城市
                    value = new Double(reqList.get(0).getEndWindow()); // 仓库的时间窗结束时间
                    value1 = new Double(reqList.get(city + 1).getEndWindow()); // 当前城市的时间窗结束时间
                    value2 = value - VRPTW.instance.distance[city + 1][0] - reqList.get(city + 1).getServiceTime();
                    value = Math.min(value1, value2);
                    a.latestTime.get(index).set(i, value);
                } else {
                    nextCity = a.tours.get(index).get(i + 1); // 下一个城市编号
                    value1 = new Double(reqList.get(city + 1).getEndWindow()); // 下一个城市的最迟到达时间
                    value2 = a.latestTime.get(index).get(i + 1) - VRPTW.instance.distance[city + 1][nextCity + 1] - reqList.get(city + 1).getServiceTime();
                    value = Math.min(value1, value2);
                    a.latestTime.get(index).set(i, value);
                }
            }
        }
    }

    /* 判断可行性，将编号为customer的城市插入到路径indexTour中，插入到previousPos后面，nextPos前面 */
    static boolean isFeasibleInsertion(Ants.Ant a, VRPTW vrp, int customer, int indexTour, int previousPos, int nextPos) {
        // 此中只考虑了插入点的可行性，未考虑插入后路径中其他点的可行性
        boolean isFeasible1 = false, isFeasible2 = false;
        double currentQuantity, arrivalTime, beginService, earliestTime, latestTime;
        double value1, value2, value3, value4;
        ArrayList<Request> reqList = vrp.getRequests();

        int previousCity = a.tours.get(indexTour).get(previousPos);
        int nextCity = a.tours.get(indexTour).get(nextPos);
        currentQuantity = a.currentQuantity.get(indexTour) + reqList.get(customer + 1).getDemand();
        arrivalTime = a.beginService[previousCity + 1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][customer + 1];
        beginService = Math.max(arrivalTime, reqList.get(customer + 1).getStartWindow());
        value1 = new Double(reqList.get(customer + 1).getStartWindow());
        value2 = a.earliestTime.get(indexTour).get(previousPos) + VRPTW.instance.distance[previousCity + 1][customer + 1] + reqList.get(previousCity + 1).getServiceTime();
        earliestTime = Math.max(value1, value2);
        value3 = new Double(reqList.get(customer + 1).getEndWindow());
        value4 = a.latestTime.get(indexTour).get(nextPos) - VRPTW.instance.distance[customer + 1][nextCity + 1] - reqList.get(customer + 1).getServiceTime();
        latestTime = Math.min(value3, value4);
        // 判断：容量限制、时间窗限制、最早到达时间小于最迟到达时间
        if ((currentQuantity <= vrp.getCapacity()) && (earliestTime <= latestTime) && (beginService <= reqList.get(customer + 1).getEndWindow())) {
            isFeasible1 = true;
        }

        if (isFeasible1) {
            isFeasible2 = checkIsFeasibleTour(a, vrp, customer, indexTour, previousPos, nextPos);
        }
        // 默认不可行
        return isFeasible2;
    }

    /* 判断将customer插入到路径indexTour中，插入到previousPos后面，nextPos前面。此路径中其他所有城市点的可行性 */
    static boolean checkIsFeasibleTour(Ants.Ant a, VRPTW vrp, int customer, int indexTour, int previousPos, int nextPos) {
        boolean res = true;
        int currentCity, prevCity;
        double currentQuantity, currentTime;
        double distance, arrivalTime, beginService;
        ArrayList<Request> reqList = vrp.getRequests();

        // 1.从仓库出发的路径载量和当前时间
        currentQuantity = reqList.get(0).getDemand(); // 初始载量为仓库的需求量
        currentTime = 0.0; // 初始时间为在仓库的时间

        // 2.第一个城市到nextPos-1的位置，计算当前时间和载量，判断时间窗约束
        // 仓库 ---> 插入位置前
        for (int currentPos = 1; currentPos < nextPos; currentPos++) {
            prevCity = a.tours.get(indexTour).get(currentPos - 1);
            currentCity = a.tours.get(indexTour).get(currentPos);
            currentQuantity += reqList.get(currentCity + 1).getDemand();

            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                return false;
            }
            currentTime = beginService;
        }

        // 3.nextPos位置插入城市，计算当前时间和载量，判断时间窗约束
        // 前一城市 ---> 插入城市
        prevCity = a.tours.get(indexTour).get(nextPos - 1);
        currentCity = customer;
        currentQuantity += reqList.get(currentCity + 1).getDemand();

        distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
        arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
        beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
        if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
            return false;
        }
        currentTime = beginService;

        // 4.nextPos+1位置，计算当前时间和载量，判断时间窗约束
        // 插入城市 ---> 插入位置下一个城市
        prevCity = customer;
        currentCity = a.tours.get(indexTour).get(nextPos);
        currentQuantity += reqList.get(currentCity + 1).getDemand();

        distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
        arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
        beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
        if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
            return false;
        }
        currentTime = beginService;

        // 5.nextPos+1到路径末尾，计算当前时间和载量，判断时间窗约束
        // 插入位置下一个城市 ---> 路径末尾
        for (int currentPos = nextPos + 1; currentPos < a.tours.get(indexTour).size(); currentPos++) {
            prevCity = a.tours.get(indexTour).get(currentPos - 1);
            currentCity = a.tours.get(indexTour).get(currentPos);
            currentQuantity += reqList.get(currentCity + 1).getDemand();

            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                //isFeasible = false;
                return false;
            }
            currentTime = beginService;
        }

        // 6. 判断载量约束
        if (currentQuantity > vrp.getCapacity()) {
            return false;
        }

        return res;
    }

    /* 执行insertion heuristic 操作后，更新每条路径中每个城市的，最早到达时间和最迟到达时间 */
    static void updateRouteVariables(Ants.Ant a, VRPTW vrp, Insertion ins) {
        int previousCity, nextCity, bestPos, bestIndexTour;
        double value1, value2, oldLatestTime, newLatestTime, oldEarliestTime, newEarliestTime;
        ArrayList<Request> reqList = vrp.getRequests();
        bestIndexTour = ins.getIndexTour(); // 插入路径
        bestPos = ins.getPreviousNode(); // 插入城市的位置

        // 更新插入城市之前城市序列的最迟到达时间
        for (int k = bestPos - 1; k >= 0; k--) {
            previousCity = a.tours.get(bestIndexTour).get(k); // 插入城市前面城市的编号
            nextCity = a.tours.get(bestIndexTour).get(k + 1); // 插入城市的编号
            // 因为是倒着计算，插入城市位置后的序列不变，前面的城市序列向前移一位。
            oldLatestTime = a.latestTime.get(bestIndexTour).get(k);
            value1 = a.latestTime.get(bestIndexTour).get(k + 1)  // 插入城市的最迟到达时间
                    - VRPTW.instance.distance[previousCity + 1][nextCity + 1] // 距离时间
                    - reqList.get(previousCity + 1).getServiceTime(); // 插入城市前面城市的服务时间
            newLatestTime = Math.min(oldLatestTime, value1);
            if (oldLatestTime != newLatestTime) {
                a.latestTime.get(bestIndexTour).set(k, newLatestTime);
            }
            else{
                break;
            }
        }

        // 更新插入城市之后城市序列的最早到达时间
        for (int k = bestPos + 1; k < a.tours.get(bestIndexTour).size(); k++) {
            previousCity = a.tours.get(bestIndexTour).get(k - 1); // 插入城市的位置
            nextCity = a.tours.get(bestIndexTour).get(k); // 插入城市后面城市的位置
            // 插入城市操作前，这个位置的城市的最早开始时间，为旧的最早到达时间
            oldEarliestTime = a.earliestTime.get(bestIndexTour).get(k);
            value2 = a.earliestTime.get(bestIndexTour).get(k - 1)  // 插入城市的最早到达时间
                    + VRPTW.instance.distance[previousCity + 1][nextCity + 1] // 路上时间
                    + reqList.get(previousCity + 1).getServiceTime(); // 插入城市的服务时间
            newEarliestTime = Math.max(oldEarliestTime, value2);
            if (oldEarliestTime != newEarliestTime) {
                a.earliestTime.get(bestIndexTour).set(k, newEarliestTime);
            }
            else {
                break;
            }
        }

        // 插入城市的最早到达时间和最迟到达时间已经在更新了，在[insertion heuristic]代码中
    }
}